#include <stdio.h>
// 直插排序
int insert_sort(int dat[],int len){
    int i,j;
    // 从dat[2]~dat[n] 依次插入到前面已经排好序的序列中
    for (i = 2; i <len ; ++i){
        // j作为游标，从当前位置依次往前比较
        j=i-1;
        // dat[0] 储存当前待插入的元素（也作游标，防止游标越界）
        dat[0] = dat[i];
        // 从待插入元素的前一个往前比较比，
        while(dat[0]<dat[j]) {
            dat[j+1] = dat[j];//比它小则向后移动
            j--;
        }
        dat[j+1] = dat[0]; //插入
    }
    return 1;
}
// 折半查找
int binary_search(int dat[],int len,int key){
    int low=1,hight = len-1,mid;
    while(low<=hight) {
        mid = (low+hight)/2;
        if(dat[mid]==key)
            return mid;
        else if(dat[mid]>key)
            hight = mid-1;
        else if(dat[mid]<key)
            low = mid+1;
    }
    return -1;
}
// 折半插入排序
int insert_sort2(int dat[],int len){
    int i,j;
    int mid,low,hight;
    for (i = 2; i < len; ++i){
        low = 1;
        hight = i-1;
        dat[0] = dat[i];
        // 折半查找 寻找插入位置
        while(low<=hight) {
            mid = (low+hight)/2;
            if(dat[mid]>dat[0])
                hight = mid - 1;
            else
                low = mid + 1;
        }
        // 找到插入位置 hight+1 移动之后的元素
        for(j=i-1; j >= hight+1; j--){
            dat[j+1]=dat[j];
        }
        dat[hight+1] = dat[0]; // 插入
    }
    return 1;
}
// 希尔排序
int shell_sort(int dat[],int len){
    int i,j,dk;
    for (dk = len/2; dk >= 1 ;dk =dk/2){
        // 内部与直插排序
        for (i = dk+1; i <= len; ++i){
            j = i-dk;dat[0] = dat[i];
            while(j>0 && dat[0]<dat[j] ) {
                dat[j+dk] = dat[j];
                j = j-dk;
            }
            dat[j+dk] = dat[0];
        }
    }
    return 1;
}
int Qk_pass(int * data,int left,int right){
    int i,j;
    int k;
    i = left; j = right;
    k = data[i];
    while(i < j){       //此次划分完成
        while(i < j && data[j]>k) j--; //从后往前找比k小的
        if (i < j){
            data[i] = data[j];    //比k小的放k前面
            i++;
        }
        while(i < j && data[i]<k) i++; //从前往后找比k大的
        if(i <j) {
            data[j] = data[i];       // 比k大的放k后面
            j--;
        }
    }
    data[i] = k;
    return i;
}
/**
 * 快排算法
 * @Author   smallcatx0
 * @DateTime 2017-03-26
 * @param    data       [数据源]
 * @param    left       [起始下标]
 * @param    right      [结束下标]
 */
void Qk_sort(int * data,int left,int right){
    if(left<right) {
        //Qk_pass() 就是一划分
        int pos = Qk_pass(data,left,right);
        Qk_sort(data,left,pos-1);
        Qk_sort(data,pos+1,right);
    }
}
// 选择排序
int select_sort(int a[],int len){
    int i,j,min;
    int temp;
    for (i=0;i<len-1; ++i){
        min = i;
        for(j=i+1;j<len;j++)
            if(a[j]<a[min]) min=j;
        if(min!=i) {
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
    return 1;
}


int main(void){
    int data[]={0,23,3,34,545,5,12,10,21,3,4,2};
    int a;
    a = sizeof(data)/sizeof(data[0]);
    // Qk_sort(data,0,len-1);
    // insert_sort(data,len);
    // insert_sort2(data,len);
    printf("%d\n",a);
    // shell_sort(data,a);
    printf("%d\n",a);
    // for (int i = 1; i <11; ++i)
    //     printf("%d ",data[i] );
    return 0;
}